package com.fr.lintcode;

public class Q1321 {

    /**
     * @param n: an integer 
     * @return: the total number of digit 1
     * Q3 的缩略版
     */
	
    public int countDigitOne(int n) {
        // write your code here
    	return digitCounts(1, n);
    }
    public int digitCounts(int k, int n) {
    	if(n < 10){
    		if(n >= k){
    			return 1;
    		}
    		return 0;
    	}
    	int sum = 0;
    	if(k == 0){
    		while(n > 0){
    			sum += n/10;
    			n=n/10;
    		}
    		return sum + 1;
    	}
    	
    	int t = 1;
        while(n >= t){
        	int t1 = t * 10;
        	sum = sum + (n/t1) * t;
        	int temp = n % t1;
        	int now = temp / t;
        	if(now > k){
        		sum = sum + t;
        	}else if(now == k){
        		int temp1 = temp % t;
        		sum = sum + temp1 + 1;
        	}
        	t = t1;
        }
        return sum;
    }
    public int digitCounts1(int k, int n) {
    	int sum = 0;
        for(int i = 0; i <= n; i ++){
        	int j = i;
        	while(j > 0){
        		int temp = j % 10;
        		if (temp == k){
        			sum ++;
        		}
        		j /= 10;
        	}
        }
        return sum;
    }
}
